package 典型.回溯法;

import java.util.ArrayList;
import java.util.List;

// 排列问题 https://leetcode-cn.com/problems/permutations/
public class LC46 {
    public static List<List<Integer>> permute(int[] nums) {
        //利用回溯法求解
        //定义一个全局变量保存所有集合
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length == 0) return res;
        // 参数:输出的结果，回调过程中已经访问的数据，原始数组
        backTrack(res, new ArrayList<>(), nums);
        return res;
    }

    public static void backTrack(List<List<Integer>> res, List<Integer> list, int[] nums) {
        //终结条件，满足条件的时候
        if (list.size() == nums.length) {
            //将满足条件的解加入到解集之中，全局添加一个满足条件的集合
            res.add(new ArrayList<>(list));
        } else {
            for (int num : nums) {
                if (list.contains(num)) continue;
                //list中不包含nums[i]的时候才添加
                list.add(num);
                //递归调用，此时的list一直在变化
                backTrack(res, list, nums);
//                System.out.println("tempList回溯之后的内容:" + list + "-------" + "i的值:" + i);
                //它移除tempList最后一个元素的作用就是返回上一次调用时的数据，也就是希望返回之前的节点再去重新搜索满足条件。这样才能实现回溯
                //移除的过程一再在做递归，同样在循环
                list.remove(list.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(permute(new int[]{1, 2, 3, 4}));
    }
}
